package cn.zifangsky.stack.questions;

import org.junit.Test;

import cn.zifangsky.stack.LinkStack;
import cn.zifangsky.stack.Stack;

/**
 * 栈中元素升序排列算法
 * @author zifangsky
 *
 */
public class Problem_005_AscendingSortStack {

	/**
	 * 思路类似于插入排序：
	 * 		每次从stack这个栈移除一个元素并将其插入到已排序的result栈的正确位置即可
	 * @时间复杂度 O(n²)
	 * @param stack
	 */
	public Stack<Integer> sort(Stack<Integer> stack){
		Stack<Integer> result = new LinkStack<>();
		
		while (!stack.isEmpty()) {
			Integer data = stack.pop();
			
			while (!result.isEmpty() && result.top() > data) {
				stack.push(result.pop());
			}
			result.push(data);
		}
		return result;
	}

	@Test
	public void testMethods(){
		Stack<Integer> stack = new LinkStack<>();
		stack.push(1);
		stack.push(6);
		stack.push(3);
		stack.push(5);
		stack.push(4);
		stack.push(2);
		
		stack = sort(stack);

		stack.print();
	}
}
